Some search engines employ rule-based grammars to route queries to corresponding domains of information to provide, for instance, instant answers for query searches. Instant answers are information provided in response to a search query in addition to typical search result that allow the user to quickly find information that they are seeking without having to sift through search results. The rule-based grammars may be used to classify search queries received at a search engine, annotate the queries, and route the queries to appropriate data sources to find and return results for the queries. For instance, suppose a user enters the search query: “weather in Seattle.” A grammar may be used to identify that Seattle is a city and weather is a keyword. The grammar may also be used to identify an appropriate data source to provide an answer (e.g., a data source containing weather information) and assists in evaluating the query to provide an appropriate response. Accordingly, by employing a grammar, weather information for Seattle could be provided as an instant answer to the search query in addition to traditional web page search results.
Grammars can be generated manually by domain experts or automatically. Most grammars used are relatively large with multiple rules and combinations of items. Optimizing such grammars to provide, for instance, instant answers to search queries has been a very difficult task. Compressing a grammar is usually not an issue for compilers, because grammar sizes are small and highly optimized with extensive iterations by experts. But for instant answers, there may be many different grammars for many different answers. Most of these grammars can be large and inefficient.